#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    char data;
    struct TreeNode *lchild;
    struct TreeNode *rchild;
    int ltag;
    int rtag;
} TreeNode;

void creatTree(TreeNode **T, char *data, int *index) 
{
    char ch = data[(*index)++];
    if ('#' == ch) {
        *T = NULL;
    } else {
        (*T) = (TreeNode *)malloc(sizeof(TreeNode));
        (*T)->data = ch;
        (*T)->ltag = 0;
        (*T)->rtag = 0;
        creatTree(&((*T)->lchild), data, index);
        creatTree(&((*T)->rchild), data, index);
    }
}

TreeNode *getNext(TreeNode *T)
{
    if (T->rtag == 1) return T->rchild;//root先访问
    if (T->ltag == 0) return T->lchild;//此时可能lchild指向它的前驱 即之前的树无左孩子
    return T->rchild;                  //树是递归的 每一个都看作根节点 有右孩子 
                                       //根左右 根之后是左判断是否有左孩子
    /*
    if (T->rtag == 1 || T->ltag ==1) return T->rchild;
    return T->lchild;//树是递归的 每一个都看作根节点 有右孩子 
    */ 
}

void preThreadTree(TreeNode *T, TreeNode **pre) //二级指针全局
{
    if (T) {
        //do something
        if (T->lchild == NULL) {
            T->lchild = *pre;
            T->ltag = 1;
        }
        if (*pre != NULL && (*pre)->rchild == NULL) {
            (*pre)->rchild = T;
            (*pre)->rtag = 1;
        }
        (*pre) = T;
        if (T->ltag == 0) {
            preThreadTree(T->lchild, pre);
        }
        preThreadTree(T->rchild, pre);
    }
}

int main(void)
{
    int index = 0;
    char *data = "AB##C##";
    TreeNode *T;
    TreeNode *pre = NULL;
    creatTree(&T, data, &index);

    preThreadTree(T, &pre);
    (pre)->rchild = NULL;
    (pre)->rtag = 1;
    for (TreeNode *node = T; node != NULL; node = getNext(node)) {
        printf("%c ", node->data);
    }

    return 0;
}